package 笔试;

import java.util.ArrayList;
import java.util.List;

public class 有效的括号字符串 {
    public boolean checkValidString (String s) {
        if(s == null || s.length() == 0) {
            return true;
        }
        // write code here
        char[] arr = s.toCharArray();
        List<Character> st = new ArrayList<Character>();
        int count = 0;
        for(char ch : arr) {
            if(ch == '(' || ch == '*') {
                st.add(ch);
                if(ch == '*') count++;
            } else {
                if(st.isEmpty()) {
                    return false;
                }

                boolean stteLeft = false;
                int size = st.size();
                for(int i = size-1; i >= 0; i--) {
                    if(st.get(i) == '(') {
                        stteLeft = true;
                        st.remove(i);
                        break;
                    }
                }
                if(!stteLeft) {
                    st.remove(size-1);
                    count--;
                }
            }
        }

        int size = st.size();
        count = 0;
        for(int i = size-1; i >= 0; i--) {
            if(st.get(i) == '(') {
                if(count <= 0) {
                    return false;
                } else {
                    count--;
                }
            } else {
                count++;
            }
        }

        return true;
    }
}
